#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"


int BinaryTreeInit(BinaryTree* tree) {
	tree->root = malloc(sizeof(BinaryTreeNode));
	if (tree->root == NULL) {
		return 1;
	}
	tree->root->data = 0;
	tree->root->left = 0;
	tree->root->right = 0;
	return 0;
}


BinaryTreeNode* BinaryTreeAppendChild(BinaryTreeNode* parent, ElemType elem, int right) {
	if ((parent->left != NULL && !right) || (parent->right != NULL && right)) {
		return NULL;
	}
	BinaryTreeNode* node = malloc(sizeof(BinaryTreeNode));
	if (node == NULL) {
		return NULL;
	}
	node->data = elem;
	node->left = NULL;
	node->right = NULL;
	if (right) {
		parent->right = node;
	}
	else {
		parent->left = node;
	}
	return node;
}


int BinaryTreePrintCore(BinaryTreeNode* root, int idx) {
	if (root == NULL) {
		return 1;
	}
	else {
		for (int x = 0; x < idx; x += 1) {
			printf("    ");
		}
		printf("%d\n", root->data);
		BinaryTreePrintCore(root->left, idx + 1);
		BinaryTreePrintCore(root->right, idx + 1);
		return 0;
	}
}


int BinaryTreePrint(BinaryTreeNode* root) {
	return BinaryTreePrintCore(root, 0);
}


// Prefix
// **** (1)
// **│* (2)
// **┌─ (3)
// **└─ (4)
// Postfix
// N─┤* (LR)
// N─┘* (L)
// N─┐* (R)
// N*** (Leaf)
int BinaryTreePrintBeautyCore(BinaryTreeNode* root, int idle[], int idx) {
	if (root->left != NULL) {
		idle[idx] = 3;
		int bk;
		if (idx > 0) {
			bk = idle[idx-1];
			if (idle[idx-1] == 3){
				idle[idx-1] = 1;
			}
			if (idle[idx-1] == 4) {
				idle[idx-1] = 2;
			}
		}
		BinaryTreePrintBeautyCore(root->left, idle, idx+1);
		if (idx > 0) {
			idle[idx-1] = bk;
		}
	}
	for (int x = 0; x < idx; x += 1) {
		if (idle[x] == 1) {
			printf("    ");
		}
		else if (idle[x] == 2) {
			printf("  │ ");
		}
		else if (idle[x] == 3) {
			printf("  ┌─");
		}
		else if (idle[x] == 4) {
			printf("  └─");
		}
	}
	printf("%d\n", root->data);
	if (root->right != NULL) {
		idle[idx] = 4;
		int bk;
		if (idx > 0) {
			if (idle[idx-1] == 3){
				idle[idx-1] = 2;
			}
			if (idle[idx-1] == 4) {
				idle[idx-1] = 1;
			}
		}
		BinaryTreePrintBeautyCore(root->right, idle, idx+1);
		if (idx > 0) {
			idle[idx-1] = bk;
		}
	}
	return 0;
}


int BinaryTreePrintBeauty(BinaryTreeNode* root) {
	if (root == NULL) {
		return 1;
	}
	int idle[1000];
	for (int idx = 0; idx < 100; idx += 1) {
		idle[idx] = 0;
	}
	return BinaryTreePrintBeautyCore(root, idle, 0);
}


BinaryTreeNode* BinaryTreeParent(BinaryTreeNode* root, BinaryTreeNode* target) {
	if (root == NULL) {
		return NULL;
	}
	if (root->left == target || root->right == target) {
		return root;
	}
	BinaryTreeNode* rtn = BinaryTreeParent(root->left, target);
	if (rtn != NULL) {
		return rtn;
	}
	rtn = BinaryTreeParent(root->right, target);
	if (rtn != NULL) {
		return rtn;
	}
	return NULL;
}


int BinaryTreeDeleteNodeCore(BinaryTreeNode* target) {
	if (target->left != NULL) {
		BinaryTreeDeleteNodeCore(target->left);
	}
	if (target->right != NULL) {
		BinaryTreeDeleteNodeCore(target->right);
	}
	free(target);
	return 0;
}


int BinaryTreeDeleteNode(BinaryTreeNode* root, BinaryTreeNode* target) {
	BinaryTreeNode* parent = BinaryTreeParent(root, target);
	if (parent == NULL) {
		return 1;
	}
	if (parent->left == target) {
		parent->left = NULL;
	}
	if (parent->right == target) {
		parent->right = NULL;
	}
	BinaryTreeDeleteNodeCore(target);
	return 0;
}


int BinaryTreeDestory(BinaryTree* tree) {
	BinaryTreeDeleteNodeCore(tree->root);
	tree->root = NULL;
	return 0;
}


int main() {
	BinaryTree tree;
	BinaryTreeInit(&tree);

	BinaryTreeAppendChild(tree.root, 2003, 0);
	BinaryTreeAppendChild(tree.root->left, 8, 0);
	BinaryTreeAppendChild(tree.root->left, 22, 1);
	BinaryTreeAppendChild(tree.root, 2006, 1);
	BinaryTreeAppendChild(tree.root->right, 6, 0);
	BinaryTreeAppendChild(tree.root->right, 6, 1);

	BinaryTreePrintBeauty(tree.root);

	BinaryTreeDeleteNode(tree.root, tree.root->left->left);

	BinaryTreePrint(tree.root);

	BinaryTreeDestory(&tree);

	return 0;
}
